package list

func sortArray(nums []int) []int {
	quickSort(0, len(nums)-1, nums)
	return nums
}

func quickSort(left, right int, nums []int) {
	if len(nums) == 0 || left >= right {
		return
	}

	i, j := left, right

	base := nums[left]
	for left < right {
		for nums[right] >= base && left < right {
			right--
		}

		for nums[left] <= base && left < right {
			left++
		}

		if left < right {
			nums[right], nums[left] = nums[left], nums[right]
		}
	}

	nums[i], nums[left] = nums[left], nums[i]

	quickSort(i, left-1, nums)
	quickSort(left+1, j, nums)

}
